#include <vector>
#include <iostream>

using namespace std;
// 埃拉托色尼素数筛
// 找出 0 ～ n 之间的所有素数
// 0 ～ 16
vector<int> primeNumbers(int n) {
  vector<bool> isNotPrime(n + 1, false);

  isNotPrime[0] = true;
  isNotPrime[1] = true;
  /*
  2 - 2 / 3 / 4 / 5 / 6 /...
  3 - 3 / 4 / 5 / ...
  */
  for (int i = 2; i * i <= n; ++i) {
    if (isNotPrime[i] == false) {
      // i 是一个素数
      // 在 isNotPrime ，标记 i 所有的倍数。
      for (int j = i * i; j <= n; j += i) {
        // 把 j 标记成合数
        isNotPrime[j] = true;
      }
    }
  }

  // 遍历 isNotPrime，其中值为 false 的索引位置，都是素数。
  vector<int> result;
  for (int i = 0; i < isNotPrime.size(); ++i) {
    if (isNotPrime[i] == false) {
      result.push_back(i);
    }
  }

  return result;
}

// 欧拉素数筛
vector<int> primes2(int n) {
  vector<bool> isNotPrime(n + 1, false);
  vector<int> numbers; // 保存所有筛选出来的素数

  isNotPrime[0] = true;
  isNotPrime[1] = true;

  for (int i = 2; i <= n; ++i) {
    // 如果 i 是素数，就添加到 numbers 里
    if (isNotPrime[i] == false) {
      numbers.push_back(i);
    }

    // 让 i 和 numbers 中的每一个数字相乘，去掉合数。
    for (int n : numbers) {
      if (n * i <= n) {
        isNotPrime[i * n] = true;
      }

      if (i % n == 0) {
        break;
      }
    }
  }
}

int main(int argc, char const *argv[])
{
  /* code */

  return 0;
}
